package main.leetcode.clockin.Auguest;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * 632. 最小区间
 *
 * <p>你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
 *
 * <p>我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。
 *
 * <p>示例 1: 输入:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]] 输出: [20,24] 解释: 列表 1：[4, 10, 15, 24,
 * 26]，24 在区间 [20,24] 中。 列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。 列表 3：[5, 18, 22, 30]，22 在区间 [20,24]
 * 中。
 *
 * <p>注意: 给定的列表可能包含重复元素，所以在这里升序表示 >= 。 1 <= k <= 3500 -105 <= 元素的值 <= 105
 * 对于使用Java的用户，请注意传入类型已修改为List<List<Integer>>。重置代码模板后可以看到这项改动。
 */
public class day1 {
    public static void main(String[] args) {
        List<List<Integer>> nums = new ArrayList<>();
        //        nums.add(Arrays.asList(-1, 2, 3));
        //        nums.add(Arrays.asList(1));
        //        nums.add(Arrays.asList(1, 2));
        //        nums.add(Arrays.asList(1, 1, 3));
        nums.add(Arrays.asList(1, 3, 5, 7, 9, 10));
        nums.add(Arrays.asList(2, 4, 6, 8, 10));
        System.out.println(Arrays.toString(new day1().smallestRange(nums)));
    }

    public int[] smallestRange(List<List<Integer>> nums) {
        int k = nums.size();
        // 记录最小值，最大值
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;

        // 构建表
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < k; ++i) {
            List<Integer> cur = nums.get(i);
            for (Integer num : cur) {
                List<Integer> list = map.getOrDefault(num, new ArrayList<>());
                list.add(i);
                map.put(num, list);
                min = Math.min(min, num);
                max = Math.max(max, num);
            }
        }

        int i = min, j = min;
        int[] res = new int[] {min, max};
        // 记录窗口内组数出现的次数
        int[] cnt = new int[k];
        int curSize = 0;
        while (j <= max) {
            if (map.containsKey(j)) {
                for (Integer integer : map.get(j)) {
                    ++cnt[integer];
                    // 更新当前窗口包含的组别数
                    if (cnt[integer] == 1) {
                        ++curSize;
                    }
                }
                while (curSize == k) {
                    if (j - i < res[1] - res[0]) {
                        res[0] = i;
                        res[1] = j;
                    }
                    if (map.containsKey(i)) {
                        for (Integer integer : map.get(i)) {
                            --cnt[integer];
                            if (cnt[integer] == 0) {
                                --curSize;
                            }
                        }
                    }
                    ++i;
                }
            }
            ++j;
        }
        return res;
    }
}
